# 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 
# 
#  给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
# 
#  
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：digits = "23"
# 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
#  
# 
#  示例 2： 
# 
#  
# 输入：digits = ""
# 输出：[]
#  
# 
#  示例 3： 
# 
#  
# 输入：digits = "2"
# 输出：["a","b","c"]
#  
# 
#  
# 
#  提示： 
# 
#  
#  0 <= digits.length <= 4 
#  digits[i] 是范围 ['2', '9'] 的一个数字。 
#  
#  Related Topics 哈希表 字符串 回溯 
#  👍 1513 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return list()
        phone_dict = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        temp = list()
        result = list()

        def back(idx):
            if idx == len(digits):
                result.append(''.join(temp))
            else:
                d = digits[idx]
                for ch in phone_dict[d]:
                    temp.append(ch)
                    back(idx + 1)
                    temp.pop()
        back(0)
        return result

# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 回溯
# 哈希表维护对应关系
# 维护已有字母排列的字符串
# 取数字对应的字母, 添加到串后

# def letterCombinations(self, digits: str) -> List[str]:
#     if not digits:
#         return list()
#     phone_dict = {
#         "2": "abc",
#         "3": "def",
#         "4": "ghi",
#         "5": "jkl",
#         "6": "mno",
#         "7": "pqrs",
#         "8": "tuv",
#         "9": "wxyz",
#     }
#
#     temp = list()
#     result = list()
#
#     def backtrack(index: int):
#         if index == len(digits):
#             result.append("".join(temp))
#         else:
#             digit = digits[index]
#             for letter in phone_dict[digit]:
#                 temp.append(letter)
#                 backtrack(index + 1)
#                 temp.pop()
#
#     backtrack(0)
#     return result



if __name__ == '__main__':
    s = Solution()
    digits = "23"
    r = s.letterCombinations(digits)
    assert r == ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"], r
